#include <bits/stdc++.h>

using namespace std;

typedef int ElemType;

//快速排序 挖坑法，王道书上使用的方法，最左边作为分割值
int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];//把最左边的值暂存起来
    while (low < high) {
        while (low < high && A[high] >= pivot)//让high从最右边找，找到比分割值小，循环结束
            --high;
        A[low] = A[high];
        while (low < high && A[low] <= pivot)//让low从最左边开始找，找到比分割值大，就结束
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

//折半查找 插入排序，考的很少
void MidInsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        A[0] = A[i];
        low = 1;
        high = i - 1;//low有序序列的开始，high有序序列的最后
        while (low <= high)//先通过二分查找找到待插入位置
        {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}

//简单选择排序
void SelectSort(ElemType A[], int n) {
    int i, j, min;//min记录最小的元素的下标
    for (i = 0; i < n - 1; i++)//最多可以为8
    {
        min = i;
        for (j = i + 1; j < n; j++)//j最多可以为9
        {
            if (A[j] < A[min])
                min = j;
        }
        if (min != i) {
            swap(A[i], A[min]);
        }
    }
}

//调整某个父亲节点
void AdjustDown(ElemType A[], int k, int len) {
    int i;
    A[0] = A[k];
    for (i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1])//左子节点与右子节点比较大小
            i++;
        if (A[0] >= A[i])
            break;
        else {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
}

//用数组去表示树   层次建树
void BuildMaxHeap(ElemType A[], int len) {
    for (int i = len / 2; i > 0; i--) {
        AdjustDown(A, i, len);
    }
}

void HeapSort(ElemType A[], int len) {
    int i;
    BuildMaxHeap(A, len);//建立大顶堆
    for (i = len; i > 1; i--) {
        swap(A[i], A[1]);
        AdjustDown(A, 1, i - 1);
    }
}

//调整子树
void AdjustDown1(ElemType A[], int k, int len) {
    int dad = k;
    int son = 2 * dad + 1; //左孩子下标
    while (son <= len) {
        if (son + 1 <= len && A[son] < A[son + 1])//看下有没有右孩子，比较左右孩子选大的
        {
            son++;
        }
        if (A[son] > A[dad])//比较孩子和父亲
        {
            swap(A[son], A[dad]);
            dad = son;
            son = 2 * dad + 1;
        } else {
            break;
        }
    }
}

void HeapSort1(ElemType A[], int len) {
    int i;
    //建立大顶堆
    for (i = len / 2; i >= 0; i--) {
        AdjustDown1(A, i, len);
    }
    swap(A[0], A[len]);//交换顶部和数组最后一个元素
    for (i = len - 1; i > 0; i--) {
        AdjustDown1(A, 0, i);//剩下元素调整为大根堆
        swap(A[0], A[i]);
    }
}

int main() {
    freopen("../Intermediate_12.txt", "r", stdin);

    return 0;
}